<!DOCTYPE HTML>
<html lang="zh-CN">

<head><meta name="generator" content="Hexo 3.9.0">
    <!-- hexo-inject:begin --><!-- hexo-inject:end --><!--Setting-->
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
    <meta http-equiv="Cache-Control" content="no-siteapp">
    <meta http-equiv="Cache-Control" content="no-transform">
    <meta name="renderer" content="webkit|ie-comp|ie-stand">
    <meta name="apple-mobile-web-app-capable" content="AncyBlog">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="format-detection" content="telephone=no,email=no,adress=no">
    <meta name="browsermode" content="application">
    <meta name="screen-orientation" content="portrait">
    <meta name="theme-version" content="1.2.3">
    <meta name="root" content="/">
    <link rel="dns-prefetch" href="http://www.anciety.de">

    <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <!--SEO-->

<meta name="keywords" content="learning,crypto">


<meta name="description" content="前言
部分参考
哈希函数
定义和安全性

定义：单向函数，固定长度

三种攻击由强到弱：

原象攻击：得到了哈希函数的逆（给定一个哈希值，得到其原文）
第二原象攻击：给定明文 \(M\) 找到 ...">


<meta name="robots" content="all">
<meta name="google" content="all">
<meta name="googlebot" content="all">
<meta name="verify" content="all">
    <!--Title-->

<title>
    
    密码学救命稻草 |
    
    AncyBlog
</title>

<link rel="alternate" href="/atom.xml" title="AncyBlog" type="application/atom+xml">


<link rel="icon" href="/favicon.png">

    

<link rel="stylesheet" href="/css/bootstrap.min.css?rev=3.3.7">
<link rel="stylesheet" href="/css/font-awesome.min.css?rev=4.7.0">
<link rel="stylesheet" href="/css/style.css?rev=@@hash">
    



<script type="text/javascript" src="https://tajs.qq.com/stats?sId=66471611" charset="UTF-8"></script><!-- hexo-inject:begin --><!-- hexo-inject:end -->


    

</head>
</html>
<!--[if lte IE 8]>
<style>
    html{ font-size: 1em }
</style>
<![endif]-->
<!--[if lte IE 9]>
<div style="ie">你使用的浏览器版本过低，为了你更好的阅读体验，请更新浏览器的版本或者使用其他现代浏览器，比如Chrome、Firefox、Safari等。</div>
<![endif]-->
<body>
    <!-- hexo-inject:begin --><!-- hexo-inject:end --><header class="main-header"  style="background-image:url(
    https://www.anciety.de/img/banner.jpg)"
     >
    <div class="main-header-box">
        <a class="header-avatar" href="/" title='Anciety'>
            <img src="/img/avatar.jpg" alt="logo头像" class="img-responsive center-block">
        </a>
        <div class="branding">
            <!--<h2 class="text-hide">Snippet主题,从未如此简单有趣</h2>-->
            
            <h2>
                Hacked By Swing
            </h2>
            
        </div>
    </div>
</header>
    <nav class="main-navigation">
    <div class="container">
        <div class="row">
            <div class="col-sm-12">
                <div class="navbar-header"><span class="nav-toggle-button collapsed pull-right" data-toggle="collapse" data-target="#main-menu" id="mnav">
                        <span class="sr-only"></span>
                        <i class="fa fa-bars"></i>
                    </span>
                    <a class="navbar-brand" href="http://www.anciety.de">
                        AncyBlog</a>
                </div>
                <div class="collapse navbar-collapse" id="main-menu">
                    <ul class="menu">
                        
                        <li role="presentation" class="text-center">
                            <a href="/"><i class="fa "></i>
                                首页</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/writeups/"><i class="fa "></i>
                                writeups</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/学习/"><i class="fa "></i>
                                学习</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/问题解决/"><i class="fa "></i>
                                问题解决</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/扯淡/"><i class="fa "></i>
                                扯淡</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/archives/"><i class="fa "></i>
                                时间轴</a>
                        </li>
                        
                    </ul>
                </div>
            </div>
        </div>
    </div>
</nav>
    <section class="content-wrap">
        <div class="container">
            <div class="row">
                <main class="col-md-8 main-content m-post">
                    <p id="process"></p>
<article class="post">
    <div class="post-head">
        <h1 id="密码学救命稻草">
            
            密码学救命稻草
            
        </h1>
        <div class="post-meta">
    
    <span class="categories-meta fa-wrap">
        <i class="fa fa-folder-open-o"></i>
        <a class="category-link" href="/categories/学习/">学习</a>
    </span>
    
    
    <span class="fa-wrap">
        <i class="fa fa-tags"></i>
        <span class="tags-meta">
            
            <a class="tag-link" href="/tags/crypto/">crypto</a> <a class="tag-link" href="/tags/learning/">learning</a>
            
        </span>
    </span>
    
    
    
    <span class="fa-wrap">
        <i class="fa fa-clock-o"></i>
        <span class="date-meta">
            2019/12/26</span>
    </span>
    
    <span class="fa-wrap">
        <i class="fa fa-eye"></i>
        <span id="busuanzi_value_page_pv"></span>
    </span>
    
    
</div>
        
        
    </div>
    
    <div class="post-body post-content">
        <h2 id="前言">前言</h2>
<p><a href="https://github.com/h3h3da/Course-review-materials" target="_blank" rel="noopener">部分参考</a></p>
<h2 id="哈希函数">哈希函数</h2>
<h3 id="定义和安全性">定义和安全性</h3>
<ul>
<li>定义：单向函数，固定长度</li>
</ul>
<p>三种攻击由强到弱：</p>
<ul>
<li><p>原象攻击：得到了哈希函数的逆（给定一个哈希值，得到其原文）</p></li>
<li><p>第二原象攻击：给定明文 <span class="math inline">\(M\)</span> 找到 <span class="math inline">\(M&#39;\)</span> 使得 <span class="math inline">\(H(M&#39;) = H(M)\)</span> ，也就是给了已知明文找到另一个明文具有相同的 hash</p></li>
<li><p>碰撞：找到任意两个消息明文使得哈希值相同</p></li>
</ul>
<h3 id="比特安全性及其原理">比特安全性及其原理</h3>
<p>比特安全性：攻破密码需要 <span class="math inline">\(2^n\)</span> 次操作，那么比特安全性为 <span class="math inline">\(n\)</span></p>
<p>生日悖论：在 <span class="math inline">\(n\)</span> 人中出现两人生日为同一天的概率大于 <span class="math inline">\(\frac{1}{2}\)</span> 需要 <span class="math inline">\(n\)</span> 最小为多少？</p>
<p>实际上比特安全性只需要出现碰撞的概率大于 <span class="math inline">\(\frac{1}{2}\)</span> ，所以在哈希函数中，碰撞比特安全性为输出长度的 <span class="math inline">\(\frac{1}{2}\)</span></p>
<p>抗原象攻击的比特安全性与哈希值长度相同，抗第二原象的比特安全性就比较奇怪了，和明文的长度有关</p>
<h3 id="常用哈希函数及其构造方式哈希值长度和安全性">常用哈希函数及其构造方式、哈希值长度和安全性</h3>
<p>构造方式：</p>
<ul>
<li>Merkle-Damgard: 把消息分块，对于每一个块都调用压缩函数(Compression Function) 进行压缩，以最终的压缩函数结果为哈希函数输出</li>
<li>Sponge: 分为吸收和挤压两个阶段，吸收阶段调用压缩函数然后每次与 padding 进行异或操作，经过反复的吸收之后，再通过挤压过程输出哈希值</li>
<li>MD 构造的问题：存在长度扩展攻击的可能</li>
</ul>
<table>
<thead>
<tr class="header">
<th>哈希函数</th>
<th>构造</th>
<th>哈希值长度</th>
<th>碰撞安全性（大多数是一半）</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>MD5</td>
<td>MD</td>
<td>128 bit</td>
<td>64</td>
</tr>
<tr class="even">
<td>SHA1</td>
<td>MD</td>
<td>160 bit</td>
<td>&lt;80</td>
</tr>
<tr class="odd">
<td>SHA2 族</td>
<td>MD</td>
<td>名称上就是，比如 SHA-256 就是 256 bit</td>
<td><span class="math inline">\(\frac{n}{2}\)</span></td>
</tr>
<tr class="even">
<td>RIPEMD-160</td>
<td>MD</td>
<td>160 bit</td>
<td>80</td>
</tr>
<tr class="odd">
<td>WhirlPool</td>
<td>Miyaguchi-Preneel （不知道是个啥，所以估计应该不考吧）</td>
<td>512</td>
<td>没说，所以不知道</td>
</tr>
<tr class="even">
<td>SM3</td>
<td>MD</td>
<td>256 bit</td>
<td>128</td>
</tr>
<tr class="odd">
<td>Sha3 族</td>
<td>Sponge</td>
<td>看名称，SHA3-224 就是 224</td>
<td><span class="math inline">\(\frac{n}{2}\)</span></td>
</tr>
</tbody>
</table>
<h3 id="哈希函数应用">哈希函数应用</h3>
<ul>
<li>Key Deriving Functions ：密钥生成</li>
<li>MAC：消息认证码</li>
<li>在签名中生成定长摘要</li>
<li>把教科书式公钥密码改为安全的加密方式</li>
<li>构造伪随机数生成器</li>
</ul>
<h2 id="分组密码">分组密码</h2>
<h3 id="对加密通信的攻击">对加密通信的攻击</h3>
<ul>
<li>唯明文攻击：只有明文</li>
<li>已知明文攻击：已经获取到了一些明文密文对，但是没有密钥，想要解密的密文不知道明文</li>
<li>选择明文攻击：可以使用加密系统进行加密，也就是可以自己选择一些明文进行加密，然后得到密文，没有密钥</li>
<li>选择密文攻击：可以任意构造一些密文进行解密</li>
<li>选择文本攻击：选择明文攻击 + 选择密文攻击</li>
</ul>
<h3 id="分组密码的定义">分组密码的定义</h3>
<p>对称密码，将明文分组进行加密，所以单次加密的长度是固定的（一个块）</p>
<h3 id="两种典型构造">两种典型构造</h3>
<ul>
<li>Feistel：右边的混入密钥（通过轮函数把密钥、右边的明文进行计算）和左边的异或，得到新的右边的内容，原来右边的内容放到左边不变，最后一轮不交换。解密和加密一样，把密钥顺序倒过来就行了。</li>
<li>SP：Substitution-Permutation，每一轮混入密钥，s-box 替换然后重新排列。最后一轮不进行重新排列，保证加密解密一致。</li>
</ul>
<h3 id="常用分组密码及其构造方式密钥长度安全性">常用分组密码及其构造方式、密钥长度、安全性</h3>
<table>
<thead>
<tr class="header">
<th>分组密码</th>
<th>构造方式</th>
<th>密钥长度</th>
<th>安全性</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>DES</td>
<td>Feistel</td>
<td>56 (8 字节，每字节有一个校验位）</td>
<td>弱</td>
</tr>
<tr class="even">
<td>3DES</td>
<td>Feistel</td>
<td>56 * 3</td>
<td>112</td>
</tr>
<tr class="odd">
<td>SM4</td>
<td>非平衡 Feistel</td>
<td>128</td>
<td>?</td>
</tr>
<tr class="even">
<td>AES</td>
<td>SP</td>
<td>128/192/256</td>
<td>强</td>
</tr>
</tbody>
</table>
<h3 id="分组密码的模式">分组密码的模式</h3>
<ul>
<li>ECB：不安全，直接分块直接加密，块与块之间的规律保留了下来</li>
<li>CBC：需要 IV ，每次加密之后和下一块异或，避免块之间的规律保留，加密不可并行，解密可以</li>
<li>CFB，OFB：不能并行，也不会不安全（主要是在校验位上存在一些优势，不管）</li>
<li>CTR：使用一个计数器规避掉块之间的规律，每个块和计数器加密后的明文异或，可以并行</li>
</ul>
<h2 id="序列密码">序列密码</h2>
<h3 id="one-time-pad">One-Time-Pad</h3>
<p>密钥和明文等长，直接异或，完美密码，但是不可用</p>
<h3 id="序列密码概念和分组密码区分">序列密码概念和分组密码区分</h3>
<p>概念：使用伪随机数流作为密钥</p>
<p>和分组密码区分：（PPT 中没有明确）不需要分组，直接可以支持变长，对错误反应敏感（分组密码 CBC 模式中如果传输错误不容易处理）</p>
<h2 id="mac-和-aead">MAC 和 AEAD</h2>
<h3 id="完整性及其对安全性的影响">完整性及其对安全性的影响</h3>
<p>完整性得不到保证可能导致传输过程中内容被中间人修改。</p>
<h3 id="mac-消息认证码算法定义">MAC 消息认证码算法定义</h3>
<p><span class="math inline">\(c = MAC(k, m)\)</span> 其中 <span class="math inline">\(k\)</span> 为 MAC 算法的密钥，<span class="math inline">\(m\)</span> 为消息。</p>
<p>MAC 与加密类似，但是不可逆。</p>
<h3 id="aead-的定义">AEAD 的定义</h3>
<p>AEAD 同时提供保密性以及完整性（认证）的加密系统。</p>
<p>（其实就是把加密过程和 MAC 过程一起考虑了，例如原来加密是由 AES 这类算法完成的，然后认证则是 MAC 算法，AEAD 就是一个算法两个都有）</p>
<p>分开的话，四种方案：</p>
<ul>
<li>先 hash 再加密</li>
<li>先认证再加密</li>
<li>先加密再认证</li>
<li>独立加密和认证</li>
</ul>
<p>然而四种都有问题，所以需要 AEAD</p>
<h3 id="常用的-mac-和-aead-模式">常用的 MAC 和 AEAD 模式</h3>
<p>MAC ：</p>
<ul>
<li>HMAC：以哈希算法为核心，所以可以支持不同的哈希算法，比如 HMAC-SHA256 , HMAC-SM3</li>
<li>CMAC：和 CBC-MAC 有点关系，CBC-MAC 和分组密码的 CBC 有点关系，所以就跟分组密码有点关系，于是有 AES-128-CMAC ，SM4-CMAC 这种用法</li>
</ul>
<p>AEAD 的模式：</p>
<ul>
<li>GCM: CM 指 Ctr Mode 所以组合一下分组密码 AES-128-GCM/AES-256-GCM , SM4-GCM</li>
<li>CCM：Ctr + CBC-MAC</li>
<li>ChaCha20-Poly1305</li>
<li>OCB</li>
</ul>
<h2 id="密码分析">密码分析</h2>
<p>两种针对 s-box 的选择明文攻击。</p>
<h3 id="差分密码分析">差分密码分析</h3>
<p>首先我们需要知道，异或其实就是加法，只不过是在不同群下的加法（mod <span class="math inline">\(2^n\)</span> 的群），那么一次加密过程其实可以认为是：<span class="math inline">\(y = f(x + key)\)</span></p>
<p>其中 f 函数是 s-box 替换操作，加法是异或。</p>
<p>假设有两个输入 <span class="math inline">\(x_1\)</span> 和 <span class="math inline">\(x_2\)</span> ，那么：</p>
<p><span class="math inline">\(y_1 = f(x_1 + key)\)</span></p>
<p><span class="math inline">\(y_2 = f(x_2 + key)\)</span></p>
<p><span class="math inline">\(\Delta x = x_2 - x_1\)</span></p>
<p><span class="math inline">\(\Delta y = f(\Delta x) = f(x_2 - x_1) = f(x_2 + key - (x_1 + key))\)</span></p>
<p>所以，如果以 <span class="math inline">\(\Delta x\)</span> 作为 <span class="math inline">\(x\)</span> 进行运算，得到的 <span class="math inline">\(\Delta y\)</span> 的结果和 key 无关，也就是说，可以认为 <span class="math inline">\(\Delta x\ xor\ key = key\)</span></p>
<p>差分分析的思路就是，如果 <span class="math inline">\(\Delta y\)</span> 和 <span class="math inline">\(\Delta x\)</span> 之间存在关系，他们自己又和 key 没有关系（这样的话，key 混入的过程不会影响其规律，排列是肯定不影响的），那么就可以去恢复一部分密钥，降低恢复的难度。</p>
<p>举例：当 <span class="math inline">\(\Delta x = 1\)</span> 出现 <span class="math inline">\(\Delta y = 1\)</span> 的可能性有 2 种，分别是 <span class="math inline">\(x_1 = 4, x_2 = 5\)</span> 和 <span class="math inline">\(x_1 = 6, x_2 = 7\)</span>，那么枚举 <span class="math inline">\(x_1\)</span> 和 <span class="math inline">\(x_2\)</span> ，保证 <span class="math inline">\(\Delta x = 1\)</span>，对他们进行加密得到 <span class="math inline">\(y_1\)</span> 和 <span class="math inline">\(y_2\)</span> 同时计算出 <span class="math inline">\(\Delta y\)</span> ，如果出现了 <span class="math inline">\(\Delta y = 1\)</span> 说明出现了 2 种情况中的一种，这样就说明现在的 <span class="math inline">\(x_1 + key\)</span> 为 4 或者 5 ，<span class="math inline">\(x_1\)</span> 已知（枚举的），key 的可能性就只有两种了，这样就可以降低枚举次数。</p>
<h3 id="线性密码分析">线性密码分析</h3>
<p>和差分密码类似，不过使用了另外的规律：</p>
<p>将输入位置挑选一些（也就是让这些位为 1 其他为 0 ）进行加法（异或），再将输出位置挑选一些进行加法操作，两者相等的关系称作线性关系。</p>
<p>在完美情况下，每一位都是独立随机的，那么概率应该每一位都是 <span class="math inline">\(\frac{1}{2}\)</span> ，然后按照乘法原理乘起来。线性密码分析就是当这个概率不是完美的时候，利用这个概率来恢复密钥。</p>
<p>分析的思路就是找到输入和输出线性关系最强（概率最大）的一些输入位置和输出位置，然后，对密钥进行枚举操作（只需要枚举存在线性关系的那些位置的密钥，这样相比枚举所有密钥就少了许多），计算这个线性关系。</p>
<p>也就是对 <span class="math inline">\(y = f(x + key)\)</span> 枚举 key ，对于每一个 key 都调整 x 的值得到一个统计。根据规律，<span class="math inline">\(y\)</span> 一些位和 <span class="math inline">\(x + key\)</span> 一些位的值各自和相等的时候出现的概率出现最大的时候就说明 key 是正确的了。（所以概率差距越大越好，这样最准确，大数定律）</p>
<h2 id="公钥密码">公钥密码</h2>
<h3 id="单向函数和单向陷门函数的定义和实例">单向函数和单向陷门函数的定义和实例</h3>
<p>单向函数：正向计算容易，反向计算困难（实例：哈希函数）</p>
<p>单向陷门函数：正向计算容易，反向计算困难，但是如果有陷门信息，反向计算比较简单（实例：整数分解，离散对数问题）</p>
<h3 id="群环域">群环域</h3>
<p>见 PPT （或者 wiki ，都有详细定义）</p>
<p>简略版：</p>
<ul>
<li>群：一个操作（加法 or 乘法），一堆对象，封闭且有逆元，注意，群不要求可交换，可交换的为交换群（阿贝尔群）</li>
<li>环：两个操作，其中的一个操作（加法）是交换群，乘法有幺元，满足结合律和分配律（乘法不是群，没有逆）</li>
<li>域：两个都是交换群</li>
</ul>
<h3 id="公钥加密的定义">公钥加密的定义</h3>
<p>密钥空间 <span class="math inline">\(K\)</span> ，明文空间 <span class="math inline">\(M\)</span> ，密文空间 <span class="math inline">\(C\)</span> ，</p>
<p>一个密钥 $k K $ 为一个元组 <span class="math inline">\((pk, sk)\)</span> 其中 <span class="math inline">\(pk\)</span> 为公钥，<span class="math inline">\(sk\)</span> 为私钥。</p>
<p>加密：<span class="math inline">\(E_{pk} = M \rightarrow C\)</span> 解密：<span class="math inline">\(D_{sk} = C \rightarrow M\)</span></p>
<p>满足：<span class="math inline">\(D_{sk}( E_{pk}(m)) = m\)</span> 对任意 <span class="math inline">\(m \in M\)</span> 成立</p>
<h3 id="欧几里得算法和扩展欧几里得算法">欧几里得算法和扩展欧几里得算法</h3>
<p>欧几里得算法：<span class="math inline">\(gcd(a, b) = gcd(b, a\ mod\ b)\)</span> 如果 <span class="math inline">\(a\ mod\ b = 0\)</span> 那么 <span class="math inline">\(gcd(b, 0) = b\)</span></p>
<p>扩展欧几里得算法：计算 <span class="math inline">\(ax + by = gcd(a, b)\)</span> 的解。</p>
<p>记号：<span class="math inline">\(gcd(a, b) = gcd(a&#39;, b&#39;) = gcd(b, a)\)</span> 也就是 <span class="math inline">\(a&#39; = b, b&#39; = a\ mod\ b\)</span></p>
<p>思路：</p>
<ul>
<li>当 <span class="math inline">\(a\ mod\ b = 0\)</span> 时，<span class="math inline">\(gcd(a, 0) = ax + by\)</span> ，显然，<span class="math inline">\(x = 1\)</span> ，<span class="math inline">\(y\)</span> 为任意值（<span class="math inline">\(b\)</span> 为 0）</li>
<li>当 <span class="math inline">\(a\ mod\ b \neq 0\)</span> 时，<span class="math inline">\(gcd(a, b) = gcd(a&#39;, b&#39;) = ax + by = a&#39;x&#39; + b&#39;y&#39;\)</span> ，此时 <span class="math inline">\(b&#39; = a\ mod\ b\)</span> 所以 <span class="math inline">\(a = kb + b&#39;\)</span>，代入，<span class="math inline">\((kb + b&#39;)x + by = a&#39;x&#39; + b&#39;y&#39; = b(kx + y) + b&#39;x = a&#39;(kx + y) + b&#39;x\)</span> ，所以 <span class="math inline">\(kx + y = x&#39;\)</span> ，<span class="math inline">\(x = y&#39;\)</span> ，再进行一步计算，得到 <span class="math inline">\(x = y&#39;, y = x&#39; - ky&#39;\)</span> ，在计算欧几里得的时候是递归计算的，所以 <span class="math inline">\(x&#39;\)</span> 和 <span class="math inline">\(y&#39;\)</span> 已经计算完了，那么就可以反推出 <span class="math inline">\(x\)</span> 和 <span class="math inline">\(y\)</span> 直到整个计算过程完成，得到 <span class="math inline">\(x\)</span> 和 <span class="math inline">\(y\)</span> 了。</li>
</ul>
<h3 id="diffie-hellmanelgamel-加密">Diffie-Hellman、ElGamel 加密</h3>
<p>DH密钥交换：利用离散对数问题，即 <span class="math inline">\(g^x \equiv y\ (\\ mod\ p)\)</span></p>
<p>交换过程，双方分别随机选群内的一个元（即 <span class="math inline">\([1, p-1]\)</span> 的一个数），得到 <span class="math inline">\(a\)</span> 和 <span class="math inline">\(b\)</span> ，然后分别计算指数 <span class="math inline">\(g^a\)</span> 和 <span class="math inline">\(g^b\)</span> ，进行密钥交换，由于双方分别有指数位，然后有对方的底数位，那么 <span class="math inline">\((g^a)^b = (g^b)^a = g^{ab}\)</span> 就得到了公共的密钥，而中间人没有 <span class="math inline">\(a\)</span> 和 <span class="math inline">\(b\)</span> ，只有 <span class="math inline">\(g^a\)</span> 和 <span class="math inline">\(g^b\)</span> 无法得到 <span class="math inline">\(g^{ab}\)</span>。</p>
<p>ElGamel 加密以 DH 为基础：</p>
<p>参数大质数 <span class="math inline">\(p\)</span> 和生成元 <span class="math inline">\(g\)</span></p>
<p>密钥（和 DH 类似）：任意挑选 <span class="math inline">\([1, p-1]\)</span> 的一个元素为私钥 <span class="math inline">\(d\)</span> ，计算 <span class="math inline">\(y = g^d\ (\ mod\ p)\)</span> 为公钥</p>
<p>加密：再挑选一个 <span class="math inline">\(r\)</span> ，计算 <span class="math inline">\(c_1 = g^r\ (\ mod\ p)\)</span> ，再计算 <span class="math inline">\(c_2 = m \times y^r\ (\\ mod\ p)\)</span> 密文为 <span class="math inline">\((c_1, c_2)\)</span></p>
<p>解密：<span class="math inline">\(m = (c_1^d)^{-1} \times c_2(\ mod\ p)\)</span></p>
<h3 id="椭圆曲线的定义和椭圆曲线算术点加倍点点的标量乘法">椭圆曲线的定义和椭圆曲线算术：点加、倍点、点的标量乘法</h3>
<p>椭圆曲线：<span class="math inline">\(y^2 = x^3 + Ax + B\)</span></p>
<p>点加：两点连线交椭圆曲线的第三点关于 x 轴的对称点</p>
<p>倍点：（倍加？）自己加自己，作切线交椭圆曲线的第三点关于 x 轴的对称点</p>
<p>点的标量乘法：连续点加 <span class="math inline">\(n\)</span> 次</p>
<p>具体计算方法：</p>
<p><span class="math inline">\(a = (x_1, y_1), b = (x_2, y_2)\)</span> 求 <span class="math inline">\(c = a + b\)</span></p>
<p>当 <span class="math inline">\(a \neq b\)</span> 时，<span class="math inline">\(k = \frac{y_2 - y_1}{x_2 - x_1}\)</span> （两点斜率），否则 <span class="math inline">\(k = \frac{3 x^2 + A}{2y}\)</span> （两端求导除一下）</p>
<p><span class="math inline">\(c = (k^2 - x_1 - x_2, k(x_1 - x_3) - y_1)\)</span> (这个只能背了）</p>
<p>注意，如果是整数，那么公式中的除法就是乘逆，然后加法减法都模 <span class="math inline">\(p\)</span> 就行了。</p>
<h3 id="椭圆曲线困难问题-ecdlp">椭圆曲线困难问题 ECDLP</h3>
<p>和 DLP 一样，只不过群内的元素变成了椭圆曲线整数时的点。</p>
<h3 id="椭圆曲线密钥长度和比特安全性的关系">椭圆曲线密钥长度和比特安全性的关系</h3>
<p>由于大步小步法，老样子，除以 2 。</p>
<h2 id="素数和素性测试">素数和素性测试</h2>
<h3 id="素数本元根primitive-roots的定义">素数、本元根（Primitive Roots）的定义</h3>
<p>素数的定义：Emmm 看着办吧</p>
<p>本元根：整数模素数 <span class="math inline">\(p\)</span> 得到的是一个域，域里边的乘法加法都是循环群（也就是一直乘一个数或是加一个数会算回来），本元根（应该也是生成元 generator ）就是指这个数自己和自己相加/相乘可以得到整个群（mod p 内的所有元素）</p>
<h3 id="费马小定理欧拉公式">费马小定理、欧拉公式</h3>
<p>费马小定理： <span class="math inline">\(a^{p - 1} \equiv 1\ (\ mod\ p)\)</span> 对模素数 p 内的任意数成立</p>
<p>欧拉公式（把费马小定理推广到合数）: <span class="math inline">\(a^{\frac{(p - 1)(q - 1)}{gcd(p-1, q-1)}} \equiv 1\ (\ mod\ pq)\)</span> 对任意 <span class="math inline">\(gcd(a, pq) = 1\)</span> 成立（如果 <span class="math inline">\(gcd(a, pq) \neq 1\)</span> 那么就为 0 了，所以最后这个情况也不用特殊记）</p>
<p>有个推论（和 RSA 原理有关，所以可以看看）：<span class="math inline">\(a^x \equiv a^{x\ mod\ (p-1)(q-1)}\ (mod\ pq)\)</span> ，证明方法可以把 <span class="math inline">\(x\ mod\ (p-1)(q-1)\)</span> 写开（万能方法，遇事不绝就写开）:<span class="math inline">\(x = k(p-1)(q-1)+r\)</span> 然后算下去。</p>
<h3 id="素数生成算法">素数生成算法</h3>
<p>有个素数理论可以得到素数的分布情况，大概意思就是还挺多的。那么找大素数的方法就是先生成一个不是偶数的大数（偶数肯定不是素数），然后用 MR 素数测试看是不是素数，由于还挺多的，所以一次不行多试几次就有了。</p>
<h3 id="miller-rabin-素数测试">Miller-Rabin 素数测试</h3>
<p>根据费马小定理，素数满足 <span class="math inline">\(a^{p-1} \equiv 1\ (mod\ p)\)</span> 对于任意 <span class="math inline">\(a\)</span> 成立，但是并不是满足这个要求的都是素数，所以再加一条 <span class="math inline">\(x^2 \equiv 1\ (\ mod\ p)\)</span> 的解，在 p 是素数的情况下只有 1 和 -1 （也就是 p-1）（模素数才是一个群，见本原根那一节，合数不一定，群保证了只有一个幺元，也就是一个 1 ，但是不是群就说不好了，比如 mod 8 的时候，<span class="math inline">\(5^2 = 25 = 1\ (mod\ 8)\)</span> 就多了一个 -1 出来）</p>
<p>所以，首先我们检查费马小定理的形式是不是满足，满足的时候还不够，接着得到一个序列，序列中 <span class="math inline">\(2^s\)</span> 是能够整除 <span class="math inline">\(p-1\)</span> 的最大的数，<span class="math inline">\(q\)</span> 是一个任意奇数：</p>
<p><span class="math inline">\(a^{p-1} = a^{2^s q}, a^{2^(s-1)q}, ..., a^q\)</span></p>
<p>这个序列中，每一个前面的数都是后一个数的平方，相当于每一步都是 <span class="math inline">\(x^2 = 1\)</span>，那么，第一个数一定为 1 （费马小定理），后面的数，要么全部为 1 ，要么第一个不是 1 的数是 -1 （也就是 p-1），像刚才 mod 8 ）的情况就不是，我们得到了其中一个为 5 ，就说明不是素数）</p>
<p>如果通过了这个测试，差不多有 <span class="math inline">\(\frac{1}{4}\)</span> 的概率不是素数，如果多测几次，概率就叠加了，于是就大概率得到一个素数。</p>
<p>具体实现的时候：</p>
<ol type="1">
<li>找一个 s 和 q 使得 <span class="math inline">\(p - 1 = 2^s q\)</span> ，再随机从 1 到 p-1 选择一个 a</li>
<li>如果 <span class="math inline">\(a^q = 1\)</span>，那么通过测试</li>
<li>计算 <span class="math inline">\(a^{2^iq} = -1\)</span> 对于 <span class="math inline">\(i = 0, .., s - 1\)</span> 是否成立，成立则通过测试</li>
<li>否则未通过</li>
</ol>
<p>其实就是倒着算。</p>
<h2 id="rsa-算法">RSA 算法</h2>
<h3 id="rsa-加密rsa-签名">RSA 加密、RSA 签名</h3>
<ol type="1">
<li>选择两个素数 p 和 q</li>
<li>计算 N = pq ，<span class="math inline">\(\phi(N) = (p-1)(q-1)\)</span></li>
<li>随机从 <span class="math inline">\([1, \phi(N)]\)</span> 选择一个公钥指数 <span class="math inline">\(e\)</span>，要求 <span class="math inline">\(gcd(e, \phi(N)) = 1\)</span></li>
<li>计算私钥 <span class="math inline">\(d = e^{-1}\ mod\ \phi(N)\)</span> ，用扩展欧几里得计算，即 <span class="math inline">\(ed + \phi(N)y = gcd(e, \phi(N)) = 1\)</span> 的其中一个解</li>
</ol>
<p>公钥：N 和 e 私钥：d</p>
<p>加密：<span class="math inline">\(c = m^e\ (\ mod\ N)\)</span> 解密：<span class="math inline">\(m = c^d = m^{ed} = 1\ (mod\ N)\)</span> 指数位 <span class="math inline">\(mod \phi(N)\)</span> ，前面欧拉公式那有推论，所以才成立。</p>
<p>签名：RSA 的公钥指数和私钥是对等的！所以用私钥加密公钥解密和公钥加密私钥解密都可以，那么签名就是倒过来，用私钥加密，公钥解密，解密了看是不是和原文相等就可以验签了（注意，公钥加密的要求是公钥加密私钥解密）</p>
<h3 id="为什么教科书-rsa-算法不安全">为什么教科书 RSA 算法不安全？</h3>
<p>教科书 RSA ：没有加入填充方案，这个时候有很多攻击手法。比如广播攻击，在一个消息被不同但互质的公钥进行多次加密的时候，可以利用中国剩余定理然后开方得到密文（详情可以看我报告的PPT，broadcast attack 部分）</p>
<h3 id="rsa-的填充方案">RSA 的填充方案</h3>
<ul>
<li>PKCS#1 v1.5 ：不安全，存在解密 Oracle （可以看出解密是否正确，从而泄漏了信息）还有一些其他的攻击方法</li>
<li>PKCS#1 v2 OAEP：带有一定随机性的填充方案，可以比较好的避免广播攻击等。</li>
<li>PSS 编码：也是 PKCS#1 v2.1 的一部分</li>
</ul>
<h2 id="数字证书和-pki">数字证书和 PKI</h2>
<h3 id="数字签名的概念和典型数字签名算法">数字签名的概念和典型数字签名算法</h3>
<p>数字签名：可以验证是谁签的名，不可以被其他人伪造（也就是只有他能签出这个签名来）</p>
<p>形式化一点，就是一个算法包括几个部分：密钥生成、签名、验签</p>
<p>密钥生成：得到公钥私钥 签名：利用私钥进行签名 验签：利用公钥对签名进行验证</p>
<p>和公钥加密相比，区别主要是公私钥反了，公钥加密里边是公钥进行加密，私钥解密，数字签名倒过来了。</p>
<p>典型算法：</p>
<ul>
<li>RSA 签名（RSA-PSS，注意 padding）</li>
<li>Schnorr 签名：DSA 的前身</li>
<li>DSA 数字签名算法，椭圆曲线上的就是 ECDSA</li>
</ul>
<p>RSA 签名前面说过了。</p>
<p>Schnorr：</p>
<p>基于离散对数问题，所以生成密钥的方法一样，选素数 <span class="math inline">\(p, g\)</span> 再选一个 <span class="math inline">\(d \in {1, 2, ..., p-1}\)</span>，计算 <span class="math inline">\(y = g^d\)</span>，签名为了避免出现得到逆，还加入一个哈希函数 <span class="math inline">\(H\)</span>。</p>
<p>签名过程：选一个 <span class="math inline">\(r\)</span> ，计算 <span class="math inline">\(c_1 = g^r\)</span> ，<span class="math inline">\(e = H(r || M)\)</span> （这个就相当于明文，但是签名最好不要有明文，所以加盐哈希一下），关键步骤是计算 <span class="math inline">\(c_2 = r - de\)</span> ，签名为 (c_2, e) 验签过程：计算 <span class="math inline">\(H(g^c_2 y^e || M)\)</span> 查看是否与 <span class="math inline">\(e\)</span> 相等</p>
<p>我这里尽量保持符号和 ElGamel 中的符号一致（但是事实上差距还是很大，记忆量有点大）</p>
<p>DSA:</p>
<p>和之前又有一些区别，生成密钥过程包括：</p>
<ol type="1">
<li>选择素数 q ,选择素数 p 使得 p-1 是 q 的倍数</li>
<li>计算 <span class="math inline">\(g := h^{\frac{p - 1}{q}}\)</span> g 不能是 1 ，如果是 1 重新算</li>
<li>选择 <span class="math inline">\(d \in {1, 2, ... q-1}\)</span> 作为私钥</li>
<li>计算 <span class="math inline">\(y = g^{d}\)</span> 作为公钥</li>
</ol>
<p>签名过程：从 1 到 q-1 选择 <span class="math inline">\(r\)</span> ，计算 <span class="math inline">\(c_1 = (g^r\ mod\ p)\ mod\ q\)</span>，如果为 0 ，重新找一个 r 。计算 <span class="math inline">\(c_2 = (r^{-1}(H(m) + d c_1)\)</span> ，如果为 0 重新找 r ，<span class="math inline">\((c_1, c_2)\)</span> 组成签名 验签过程：计算 <span class="math inline">\(w = c_2^{-1}\ mod\ q\)</span>，计算 <span class="math inline">\(u_1 = H(m)\times w\ mod\ q\)</span> ，<span class="math inline">\(u_2 = c_1 \times w\ mod q\)</span> 计算 <span class="math inline">\(v = (g^{u_1} y^{u_2}\ mod\ p)\ moq\ q\)</span> 如果 v 和 <span class="math inline">\(c_1\)</span> 相等则通过</p>
<p>(这两个签名太复杂了，就是一堆构造变形，而且和 ElGamel 相似但是容易弄混，根本记不住，不知道咋办，我反正是不背了）</p>
<h3 id="数字证书根证书证书链capki-的概念通过浏览器观察网站的证书链了解现实中证书的各个域dvevov-的区别">数字证书、根证书、证书链、CA、PKI 的概念，通过浏览器观察网站的证书链，了解现实中证书的各个域，DV/EV/OV 的区别</h3>
<p>（这一部分我完全不知道怎么复习，都背下来？完全不可能，学文科差不多）</p>
<p>数字证书：一段电子文档，包括公钥、一些相关信息和颁发者签名 根证书：证书链的根，验证的开始 证书链：从根证书开始，一个颁发给另一个，形成一个链，可以从根证书开始验证 CA：证书权威机构 Certification Authority ，一个公司或者组织负责验证证书的拥有者确实拥有某个实体，然后颁发证书 PKI：公钥基础建设，是一组由硬件、软件、参与者、管理政策与流程组成的基础架构，其目的在于创造、管理、分配、使用、存储以及撤销数字证书。</p>
<p>观察证书链。。。不知道咋复习</p>
<p>证书的域：</p>
<ul>
<li>版本</li>
<li>序列号</li>
<li>签名算法</li>
<li>颁发者</li>
<li>有效期</li>
<li>客体：证书拥有者的可辨识名</li>
<li>公钥</li>
<li>扩展就不管了</li>
</ul>
<p>DV/EV/OV 的区别：</p>
<ul>
<li>DV：Domain Validation，验证拥有域名即可</li>
<li>OV：Organization Validation，需要身份权限的认证</li>
<li>EV：Extended Validation，也是身份全县认证，但是要求更高</li>
</ul>
<p>浏览器里 url 栏里 https 的地方看不到公司名字的是 DV ，看的到的一般是 OV 或者 EV。</p>
<h3 id="基于身份的密码定义典型构造应用以及和传统公钥密码pki-的区别">基于身份的密码定义、典型构造、应用以及和传统公钥密码/PKI 的区别</h3>
<p>我基本放弃这一部分了。。。</p>
<p>身份就是指一个没有加密的任意的内容，比如一个任意的字符串（邮箱之类的），基于身份的密码就是利用一个公认的 PKG (Public Key Generator)，PKG 发布一个主公钥，自己得到一个主私钥，每一方利用自己的身份从主公钥得到自己的私钥，然后向 PKG 要一个私钥。</p>
<p>典型构造：</p>
<p>不知道，又是一大堆构造，这个真没办法了。。</p>
<p>应用和区别：</p>
<ul>
<li>作为 PKI 的替代，不需要密钥和证书管理</li>
<li>公钥过期机制</li>
<li>解密密钥分发</li>
</ul>
<h2 id="数学困难问题">数学困难问题</h2>
<h3 id="离散对数问题ec-离散对数问题整数分解问题dh-问题ecdh-问题rsa-问题">离散对数问题、EC 离散对数问题、整数分解问题、DH 问题、ECDH 问题、RSA 问题</h3>
<p>前面基本已经有了</p>
<h3 id="平滑数的概念及应用">平滑数的概念及应用</h3>
<p>平滑数：一个数被分解成质因数之后最大的质因数为 n 那么这个数就是 n-平滑的，一般来说平滑数就是指这个 n 比较小，那么这个时候这个数就比较容易被分解。</p>
<h3 id="大步小步法和-pohlig-hellman-算法">大步小步法和 Pohlig-Hellman 算法</h3>
<p>这两种算法都是算离散对数问题的。</p>
<p>大步小步法：</p>
<p>计算 <span class="math inline">\(g^x = y\ (mod\ p)\)</span>，把 x 分开，写成 <span class="math inline">\(x = i\sqrt{p} + j\)</span> ，之后：</p>
<p><span class="math inline">\(g^x = g^{i\sqrt{p} + j} = g^{i\sqrt{p}} \times g^j = y\ (mod\ p)\)</span></p>
<p><span class="math inline">\(g^j = y \times (g^{-\sqrt{p}})^i\)</span></p>
<p>这个时候 <span class="math inline">\(0 &lt; i &lt; \sqrt{p}, 0 &lt; j &lt; \sqrt{p}\)</span> , 所以可以把 <span class="math inline">\(g^j\)</span> 可能的值都算出来，然后再去找 <span class="math inline">\(i\)</span> ，看不同的 <span class="math inline">\(i\)</span> 是否会算出已经算好的 <span class="math inline">\(g^j\)</span> ，这样就相当于用一些内存减少了运算时间。</p>
<p>Pohlig-Hellman：</p>
<p>前提：<span class="math inline">\(p - 1\)</span> 是平滑的，那么 <span class="math inline">\(p - 1\)</span> 很容易被分解，简单情况假设分解为 <span class="math inline">\(p - 1 = q_1 q_2\)</span></p>
<p>那么由费马小定理，<span class="math inline">\(g^{q_1 q_2} = 1\ (mod\ p)\)</span> ，这个时候，把 <span class="math inline">\(g^x = y\ (mod\ p)\)</span> 两边同时进行 <span class="math inline">\(q_1\)</span> 次方运算，得到：</p>
<p><span class="math inline">\(g^{x q_1} = y^{q_1}\ (mod\ p)\)</span></p>
<p>设 <span class="math inline">\(x_1 = x\ (mod\ q_2)\)</span> 也就是 <span class="math inline">\(x = x_1 + k q_2\)</span> ，那么 <span class="math inline">\(g^{x q_1} = g^{(x_1 + k q_2)q_1} = g^{x_1 q_1} g^{k q_1 q_2} = (g^{q_1})^{x_1} = y^{q_1}\ (mod\ p)\)</span></p>
<p>(遇事不绝就写开）</p>
<p>同理对 <span class="math inline">\(q_2\)</span> 也来这么一发，就得到了两个式子：</p>
<p><span class="math inline">\((g^{q_1})^{x_1} = y^{q_1}\ (mod\ p)\)</span></p>
<p><span class="math inline">\((g^{q_2})^{x_2} = y^{q_2}\ (mod\ p)\)</span></p>
<p>其中 <span class="math inline">\(x_1\)</span> 和 <span class="math inline">\(x_2\)</span> 都是更小的范围了，那么就可以分别把这两个求出来，然后由：</p>
<p><span class="math inline">\(x_1 = x\ (mod\ q_2)\)</span></p>
<p><span class="math inline">\(x_2 = x\ (mod\ q_1)\)</span></p>
<p>这个形式是符合中国剩余定理的形式的，所以可以用中国剩余定理求到 <span class="math inline">\(x\)</span></p>
<h2 id="硬件安全">硬件安全</h2>
<h3 id="密码硬件安全等级-1-到-4-级的主要特征">密码硬件安全等级 1 到 4 级的主要特征</h3>
<p>FIPS 140-2:</p>
<ul>
<li>第一级：物理上没什么要求，算法至少得是经过验证的算法（常用的就差不多，意思就不能是自己发明的什么乱七八糟的），实例：个人电脑的加密板</li>
<li>第二级：要求显示篡改证据，我理解就是如果被人物理搞了应该有明显痕迹可以看出来被改过，但是没有办法防止攻击者拿到想要的，只能事后。</li>
<li>第三级：有了防护机制，我理解就是如果被人物理层次搞了，会直接归零掉，所以物理攻击比较难拿到有用的信息了。</li>
<li>第四级：最强的，啥时候都不让攻破</li>
</ul>
<h3 id="测信道攻击的种类">测信道攻击的种类</h3>
<ul>
<li>能量分析攻击</li>
<li>电磁分析攻击</li>
<li>错误攻击</li>
<li>DMA 攻击</li>
<li>冷启动攻击</li>
</ul>
<h2 id="密文计算算法">密文计算算法</h2>
<h3 id="一大堆概念">一大堆概念</h3>
<p>同态加密：同态是群论就有的概念，一个同态映射 f 满足 <span class="math inline">\(f(x + y) = f(x) + f(y)\)</span> 且没有一一对应要求就是同态，如果一一对应就是 Isomorphism 。在这里 f 就是加密，所以就是加密之后进行运算和加密前进行运算一样，如果支持的是加法就是加法同态，乘法就是乘法同态。</p>
<p>基于属性的加密：就是加密之后，除了需要密钥还需要属性正确才可以进行正确解密</p>
<p>可搜索加密：加密之后可以建立索引进行搜索</p>
<p>秘密分享/秘密分割：加密之后，需要有多个人的密钥一起才能够进行解密</p>
<p>零知识证明：要证明自己有做什么事情的能力，但是又不真的做这个事情，比如要证明我拥有对某个大整数的分解，但是我又不能将这个分解告诉你，所以通过用他解决一些问题来让你知道</p>
<p>承诺：进行一个承诺保证一个值，但是又不让人知道这个值</p>
<p>隐私信息获取：想要从服务器获取一个信息，但是又不想让人知道获取的信息是什么，那么就可以获取一堆信息，其中包含真正的信息</p>
<p>不经意传输：在隐私信息获取的基础上，还不能获取到除了自己想获取的信息以外的别的信息</p>
<h3 id="典型同态加密算法支持的密文计算能力">典型同态加密算法支持的密文计算能力</h3>
<ul>
<li>Goldwasser-Micali: 异或同态</li>
<li>Paillier: 加法同态</li>
<li>ElGamel: 乘法同态</li>
<li>EC-ElGamel: 加法同态</li>
<li>Boneh-Goh-Nissim: BGN，支持最高二次的多项式运算（加法乘法）</li>
</ul>

    </div>
    
    <div class="post-footer">
        <div>
            
            转载声明：
            商业转载请联系作者获得授权,非商业转载请注明出处 © <a href="" target="_blank">Snippet</a>
            
            
        </div>
        <div>
            
        </div>
    </div>
</article>
<div class="article-nav prev-next-wrap clearfix">
    
    <a href="/2020/02/09/codegate-2020/" class="pre-post btn btn-default" title='codegate-2020-1'>
        <i class="fa fa-angle-left fa-fw"></i><span class="hidden-lg">上一篇</span>
        <span class="hidden-xs">
            codegate-2020-1</span>
    </a>
    
    
    <a href="/2019/11/05/shallow-talks-on-fp/" class="next-post btn btn-default" title='浅谈函数式编程（1）'>
        <span class="hidden-lg">下一篇</span>
        <span class="hidden-xs">
            浅谈函数式编程（1）</span><i class="fa fa-angle-right fa-fw"></i>
    </a>
    
</div>

<div id="comments">
    

<div id="vcomments" class="valine"></div>
<!--<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="/assets/valine.min.js"></script>-->
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script>
<script>
new Valine({
    av: AV,
    el: '#vcomments',
    appId: 'sBJ8fsglfz3e3AeXQbE8d8H8-gzGzoHsz',
    appKey: 'WFXH17M73py6bGqWl0ffMbHG',
    placeholder: '说点什么吧',
    notify: false,
    verify: true,
    avatar: 'mm',
    meta: 'nick,mail'.split(','),
    pageSize: '10',
    path: window.location.pathname,
    lang: 'zh-CN'.toLowerCase()
})
</script>



</div>


                </main>
                
                    <aside id="article-toc" role="navigation" class="col-md-4">
    <div class="widget">
        <h3 class="title">
            文章目录
        </h3>
        
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#前言"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#哈希函数"><span class="toc-text">哈希函数</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#定义和安全性"><span class="toc-text">定义和安全性</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#比特安全性及其原理"><span class="toc-text">比特安全性及其原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#常用哈希函数及其构造方式哈希值长度和安全性"><span class="toc-text">常用哈希函数及其构造方式、哈希值长度和安全性</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#哈希函数应用"><span class="toc-text">哈希函数应用</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#分组密码"><span class="toc-text">分组密码</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#对加密通信的攻击"><span class="toc-text">对加密通信的攻击</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#分组密码的定义"><span class="toc-text">分组密码的定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#两种典型构造"><span class="toc-text">两种典型构造</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#常用分组密码及其构造方式密钥长度安全性"><span class="toc-text">常用分组密码及其构造方式、密钥长度、安全性</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#分组密码的模式"><span class="toc-text">分组密码的模式</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#序列密码"><span class="toc-text">序列密码</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#one-time-pad"><span class="toc-text">One-Time-Pad</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#序列密码概念和分组密码区分"><span class="toc-text">序列密码概念和分组密码区分</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#mac-和-aead"><span class="toc-text">MAC 和 AEAD</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#完整性及其对安全性的影响"><span class="toc-text">完整性及其对安全性的影响</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#mac-消息认证码算法定义"><span class="toc-text">MAC 消息认证码算法定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#aead-的定义"><span class="toc-text">AEAD 的定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#常用的-mac-和-aead-模式"><span class="toc-text">常用的 MAC 和 AEAD 模式</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#密码分析"><span class="toc-text">密码分析</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#差分密码分析"><span class="toc-text">差分密码分析</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#线性密码分析"><span class="toc-text">线性密码分析</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#公钥密码"><span class="toc-text">公钥密码</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#单向函数和单向陷门函数的定义和实例"><span class="toc-text">单向函数和单向陷门函数的定义和实例</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#群环域"><span class="toc-text">群环域</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#公钥加密的定义"><span class="toc-text">公钥加密的定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#欧几里得算法和扩展欧几里得算法"><span class="toc-text">欧几里得算法和扩展欧几里得算法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#diffie-hellmanelgamel-加密"><span class="toc-text">Diffie-Hellman、ElGamel 加密</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#椭圆曲线的定义和椭圆曲线算术点加倍点点的标量乘法"><span class="toc-text">椭圆曲线的定义和椭圆曲线算术：点加、倍点、点的标量乘法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#椭圆曲线困难问题-ecdlp"><span class="toc-text">椭圆曲线困难问题 ECDLP</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#椭圆曲线密钥长度和比特安全性的关系"><span class="toc-text">椭圆曲线密钥长度和比特安全性的关系</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#素数和素性测试"><span class="toc-text">素数和素性测试</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#素数本元根primitive-roots的定义"><span class="toc-text">素数、本元根（Primitive Roots）的定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#费马小定理欧拉公式"><span class="toc-text">费马小定理、欧拉公式</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#素数生成算法"><span class="toc-text">素数生成算法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#miller-rabin-素数测试"><span class="toc-text">Miller-Rabin 素数测试</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#rsa-算法"><span class="toc-text">RSA 算法</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#rsa-加密rsa-签名"><span class="toc-text">RSA 加密、RSA 签名</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#为什么教科书-rsa-算法不安全"><span class="toc-text">为什么教科书 RSA 算法不安全？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#rsa-的填充方案"><span class="toc-text">RSA 的填充方案</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#数字证书和-pki"><span class="toc-text">数字证书和 PKI</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#数字签名的概念和典型数字签名算法"><span class="toc-text">数字签名的概念和典型数字签名算法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#数字证书根证书证书链capki-的概念通过浏览器观察网站的证书链了解现实中证书的各个域dvevov-的区别"><span class="toc-text">数字证书、根证书、证书链、CA、PKI 的概念，通过浏览器观察网站的证书链，了解现实中证书的各个域，DV/EV/OV 的区别</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#基于身份的密码定义典型构造应用以及和传统公钥密码pki-的区别"><span class="toc-text">基于身份的密码定义、典型构造、应用以及和传统公钥密码/PKI 的区别</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#数学困难问题"><span class="toc-text">数学困难问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#离散对数问题ec-离散对数问题整数分解问题dh-问题ecdh-问题rsa-问题"><span class="toc-text">离散对数问题、EC 离散对数问题、整数分解问题、DH 问题、ECDH 问题、RSA 问题</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#平滑数的概念及应用"><span class="toc-text">平滑数的概念及应用</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#大步小步法和-pohlig-hellman-算法"><span class="toc-text">大步小步法和 Pohlig-Hellman 算法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#硬件安全"><span class="toc-text">硬件安全</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#密码硬件安全等级-1-到-4-级的主要特征"><span class="toc-text">密码硬件安全等级 1 到 4 级的主要特征</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#测信道攻击的种类"><span class="toc-text">测信道攻击的种类</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#密文计算算法"><span class="toc-text">密文计算算法</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#一大堆概念"><span class="toc-text">一大堆概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#典型同态加密算法支持的密文计算能力"><span class="toc-text">典型同态加密算法支持的密文计算能力</span></a></li></ol></li></ol>
        
    </div>
</aside>
                
            </div>
        </div>
    </section>
    <footer class="main-footer">
    <div class="container">
        <div class="row">
        </div>
    </div>
</footer>
<a id="back-to-top" class="icon-btn hide">
    <i class="fa fa-chevron-up"></i>
</a>
    <div class="copyright">
    <div class="container">
        <div class="row">
            <div class="col-sm-12">
                <div class="busuanzi">
    
    访问量:
    <strong id="busuanzi_value_site_pv">
        <i class="fa fa-spinner fa-spin"></i>
    </strong>
    &nbsp; | &nbsp;
    访客数:
    <strong id="busuanzi_value_site_uv">
        <i class="fa fa-spinner fa-spin"></i>
    </strong>
    
</div>
            </div>
            <div class="col-sm-12">
                <span>Copyright &copy;
                    2019
                </span> |
                <span>
                    Powered by <a href="//hexo.io" class="copyright-links" target="_blank" rel="nofollow">Hexo</a>
                </span> |
                <span>
                    Theme by <a href="//github.com/shenliyang/hexo-theme-snippet.git" class="copyright-links" target="_blank" rel="nofollow">Snippet</a>
                </span>
            </div>
        </div>
    </div>
</div>


<script src="/assets/tagcanvas.min.js?rev=2.9"></script>
<script>
var tagOption = {
    textColour: '#444', // 字体颜色
    outlineMethod: 'block', // 选中模式
    outlineColour: '#FFDAB9', // 选中模式的颜色
    interval: 30 || 30, // 动画帧之间的时间间隔，值越大，转动幅度越大
    textHeight: 13,
    outlineRadius: 3,
    freezeActive: true || '', // 选中的标签是否继续滚动
    frontSelect: true || '', // 不选标签云后部的标签
    initial: [0.1, -0.1],
    depth: 0.5,
    decel: 0.95,
    maxSpeed: 0.03,
    reverse: true || '', // 是否反向触发
    fadeIn: 500, // 进入动画时间
    wheelZoom: false || '' // 是否启用鼠标滚轮
}
TagCanvas.Start('tag-cloud-3d', '', tagOption);
</script>


<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<script src="/js/app.js?rev=@@hash"></script><!-- hexo-inject:begin --><!-- hexo-inject:end -->
</body>
</html>